0861. 翻转矩阵后的得分【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给你一个大小为 m x n 的二元矩阵 grid，矩阵中每个元素的值为 0 或 1。

一次 移动 是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的 得分 就是这些数字的总和。

在执行任意次 移动 后（含 0 次），返回可能的最高分数。

---

示例 1：

输入：grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

示例 2：

输入：grid = [[0]]
输出：1

---

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• grid[i][j] 为 0 或 1

2. 🎯 s.1 - 贪心

c

int matrixScore(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    for (int i = 0; i < m; i++)
        if (grid[i][0] == 0)
            for (int j = 0; j < n; j++) grid[i][j] ^= 1;
    int res = 0;
    for (int j = 0; j < n; j++) {
        int ones = 0;
        for (int i = 0; i < m; i++) ones += grid[i][j];
        int mx = ones > m - ones ? ones : m - ones;
        res += mx * (1 << (n - 1 - j));
    }
    return res;
}

js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var matrixScore = function (grid) {
  const m = grid.length,
    n = grid[0].length
  for (let i = 0; i < m; i++) {
    if (grid[i][0] === 0) {
      for (let j = 0; j < n; j++) grid[i][j] ^= 1
    }
  }
  let res = 0
  for (let j = 0; j < n; j++) {
    let ones = 0
    for (let i = 0; i < m; i++) ones += grid[i][j]
    res += Math.max(ones, m - ones) * (1 << (n - 1 - j))
  }
  return res
}

py

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] ^= 1
        res = 0
        for j in range(n):
            ones = sum(grid[i][j] for i in range(m))
            res += max(ones, m - ones) * (1 << (n - 1 - j))
        return res

• 时间复杂度：$O(m\times n)$，其中 m 和 n 是矩阵的行数和列数
• 空间复杂度：$O(1)$

算法思路：

• 先确保每行首位为 1（高位价值最大），必要时翻转整行
• 再对每列，取 1 的数量和 0 的数量中的较大值作为该列贡献